\documentclass[12pt, a4paper, twoside]{ctexbook}
\usepackage[top=2.5cm, bottom=2.5cm, left=2cm, right=2cm]{geometry}
\usepackage{eso-pic, amsmath, amsthm, amssymb, bm, graphicx, transparent, mathrsfs, tikz, tikz-cd, pgfplots, fancyhdr, booktabs, mathtools, url, xcolor, listings}

\usepackage[hidelinks, colorlinks=true, linkcolor=blue]{hyperref} %这个负责交叉引用, [取消红框]

% for adjustwidth environment
\usepackage[strict]{changepage}

% for formal definitions
\usepackage{framed}

% environment derived from framed.sty: see leftbar environment definition
%------------------------------------------------------

\usepackage{tikz}
\usepackage{tikz,fullpage}
\usetikzlibrary{arrows,%
                petri,%
                topaths}%
\usepackage{tkz-berge}
\usepackage[position=top]{subfig}

\lstset{
    language=Python,            % 指定语言为Python
    basicstyle=\ttfamily,       % 基础字体为等宽字体
    keywordstyle=\color{blue},  % 关键字颜色
    stringstyle=\color{red},    % 字符串颜色
    commentstyle=\color{green!40!black}, % 注释颜色
    showstringspaces=false,     % 不显示字符串中的空格
    numbers=left,               % 行号在左侧
    numberstyle=\small,        % 行号字体大小
    breaklines=true,            % 长代码自动换行
}


\usepgfplotslibrary{patchplots}
\usetikzlibrary{patterns, positioning, arrows}
\pgfplotsset{compat=1.15}

\title{{\Huge{\textbf{Foundations of Graph Theory}}}\\——\,应用数学前沿专题课程笔记}
\author{唐嘉琪}
\date{\today}
\linespread{1.25}
\newtheorem{theorem}{定理}[section]
\newtheorem{definition}[theorem]{定义}
\newtheorem{lemma}[theorem]{引理}
\newtheorem{corollary}[theorem]{推论}
\newtheorem{example}[theorem]{例}
\newtheorem{proposition}[theorem]{命题}
\newtheorem{recall}[theorem]{回忆}
\newtheorem{rmk}[theorem]{注}

\numberwithin{equation}{section}
% 这里给出水印
\newcommand\BackgroundPicture{%
  \put(0,0){%
    \parbox[b][\paperheight]{\paperwidth}{%
      \vfill
      \centering%
\begin{tikzpicture}[remember picture,overlay]
\node [rotate=45,scale=5,text opacity=0.07] at (current page.center) {\songti 图论初步\,\,唐嘉琪}; %中括号内是[旋转角度, 字体大小, 透明度]
\end{tikzpicture}%
      \vfill
    }}}

\pagestyle{fancy}
\begin{document}

\maketitle
\begin{center}
	{\color{blue} 编译时间 \today}
\end{center}
\begin{flushleft}
Paper Size: A4\\
Book Homepage: \url{www.cnblogs.com/TangJiaqiMath/p/18955483}\\ % 这里给出书本主页的网址url
Tang Jiaqi\quad |\quad Shanghai Lixin University of Accounting and Finance\\
Personal Hompage: \url{www.cnblogs.com/TangJiaqiMath}
\end{flushleft}
\newpage

\pagenumbering{roman}
\setcounter{page}{1}
\fancyhead[R]{\vspace{1pt}\songti 唐嘉琪} % 页眉右侧内容
\fancyhead[C]{\vspace{1pt}图论初步——前言} % 页眉中间部分
\fancyhead[L]{\includegraphics[width=4cm]{../../旧机资料/识别/校名}} % 页眉左侧内容, 视情况是否添加
\setlength{\headsep}{30pt}  % 设为 30pt,可按需改(如 5pt、15pt 等)
%\fancyhead[C]{现代几何学导论——前言} % 注意修改
%\fancyhead[R]{唐嘉琪}

\AddToShipoutPicture{\BackgroundPicture}
\pagenumbering{roman}
\setcounter{page}{1}

\begin{center}
    \Huge\textbf{前言}
\end{center}~\

课程教材与参考用书选取为
\begin{center}
	\kaishu J.A.Bondy, U.S.R.Murty: Graph Theory. Springer(GTM244).\\
	\kaishu 邦迪: 图论及其应用. 高等教育出版社(2005).
\end{center}

~\\
\begin{flushright}
    \begin{tabular}{c}
        唐嘉琪\\
        \today \\
        于上海
    \end{tabular}
\end{flushright}
	\begin{figure}[htbp]%这是一个图片插入模版
		\centering
		\includegraphics[width=0.5\textwidth]{../模版/pic1}
		\label{fig:前言}%这里是交叉应用
	\end{figure}
\newpage
\pagenumbering{Roman}
\setcounter{page}{1}
\tableofcontents
\newpage
\setcounter{page}{1}
\pagenumbering{arabic}
\fancyhf{} % 清除默认的页眉页脚内容
\fancyhead[R]{\vspace{1pt}\songti 唐嘉琪} % 页眉右侧内容
\fancyhead[C]{\vspace{1pt}\leftmark} % 页眉中间部分
\fancyhead[L]{\includegraphics[width=4cm]{../../旧机资料/识别/校名}} % 页眉左侧内容, 视情况是否添加
\setlength{\headsep}{30pt}  % 设为 30pt,可按需改(如 5pt、15pt 等)
\fancyfoot[C]{\thepage} % 页码指标
\chapter{图}
现实生活中, 我们关心给定的点之间是否被线连接, 而具体的连接方式则无关紧要, 从而我们抽象出了图论.
\section{The Basic Concepts of Graph and Their Representation}
\subsection{Basic Definition of Graphs}
\begin{definition}[图的基本概念]
	图$G$是一个有序三元组$\big(V(G),E(G),\psi_G\big)$, 其中$V(G)$表示一组\textbf{顶点}(vertices), $E(G)$表示一组\textbf{边}(edge), $\psi_G$表示其上一个\textbf{关联函数}(incidence function). 参数$|V(G)|$与$|E(G)|$称为图$G$的\textbf{阶数}(order)与\textbf{大小}(size).

	若$e$是图$G$的一条边, 其顶点为$v_1$与$v_2$, 则$\psi_G(e)=\{v_1,v_2\}$, 此时称$e$\textbf{连接}(join)了$v_1$与$v_2$. $v_1$与$v_2$被称为$e$的端点(end).
	\footnote{A graph G is an ordered pair $\big(V(G),E(G)\big)$ consisting of a set $V (G)$ of vertices and a set $E(G)$, disjoint from $V (G)$, of edges, together with an incidence function $\psi_G$ that associates with each edge of $G$ an unordered pair of (not necessarily distinct) vertices of $G$. If $e$ is an edge and $u$ and $v$ are vertices such that $\psi_G(e) =\{u,v\}$, then $e$ is said to join $u$ and $v$, and the vertices $u$ and $v$ are called the ends of $e$. We denote the numbers of vertices and edges in $G$ by $v(G)$ and $e(G)$; these two basic parameters are called the order and size of $G$, respectively.}
\end{definition}

\begin{rmk}
	 为了方便书写, 我们用$v_1v_2$来表示无序对$\{v_1,v_2\}$.
	 \footnote{For notational simplicity, we write $uv$ for the unordered pair $\{u,v\}$.}
\end{rmk}
\begin{example}
	
\begin{figure}[htbp!]
	\centering
	\subfloat[示例1]{
	\label{subfig:1}
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=0,L=$x$]{x}
		\Vertex[x=-2,y=3,L=$y$]{y}
		\Vertex[x=1,y=4,L=$u$]{u}
		\Vertex[x=4,y=0,L=$w$]{w}
		\Vertex[x=4,y=2,L=$v$]{v}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
		\Edge[label=$c$](v)(w)
  		\tikzstyle{EdgeStyle}=[bend left]%向左弯曲, 红色, 箭头
  		\Edge[label=$h$](x)(y)
  		\Edge[label=$f$](x)(w)
  		\Edge[label=$a$](u)(v)
  		\Edge[label=$g$](x)(u)
  		\tikzstyle{EdgeStyle}=[bend right]
  		\Edge[label=$d$](x)(w)
  		\tikzstyle{EdgeStyle}=[loop, looseness=20, out=-100, in=-30]
  		\Edge[label=$b$](u)(u)
  		\node at (1,-1.6){$G$};
	\end{tikzpicture}
	}\quad\quad
	\subfloat[示例2]{
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=0,L=$v_0$]{0}
		\Vertex[x=0,y=2.5,L=$v_1$]{1}
		\Vertex[x=2.3,y=0.5,L=$v_2$]{2}
		\Vertex[x=1.5,y=-2,L=$v_3$]{3}
		\Vertex[x=-1.5,y=-2,L=$v_4$]{4}
		\Vertex[x=-2.3,y=0.5,L=$v_5$]{5}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
		\Edge[label=$e_6$](0)(1)
		\Edge[label=$e_7$](0)(2)
		\Edge[label=$e_8$](0)(3)
		\Edge[label=$e_9$](0)(4)
		\Edge[label=$e_{10}$](0)(5)
		\Edge[label=$e_1$](1)(2)
		\Edge[label=$e_2$](2)(3)
		\Edge[label=$e_3$](3)(4)
		\Edge[label=$e_4$](4)(5)
		\Edge[label=$e_5$](5)(1)
		\node at (0,-3){$H$};
	\end{tikzpicture}
	}
	\caption{两个例子}
	\label{fig:1-1_two_examples}
\end{figure}
图\ref{fig:1-1_two_examples}给出了两个图: 图$G$与图$H$.

对于图$G$, $G=\big(V(G),E(G),\psi_G\big)$, where
\begin{align*}
	V(G)&=\{u,v,w,x,y\},\quad E(G)=\{a,b,c,d,e,f,g,h\}.\\
	\psi_G &\colon \begin{tabular}{llll}
		$a\mapsto uv$ & $b\mapsto uu$ & $c\mapsto vw$ & $d\mapsto wx$\\
		$e\mapsto vx$ & $f\mapsto wx$ & $g\mapsto ux$ & $h\mapsto xy$
	\end{tabular}
\end{align*}

对于图$H$, $H=\big(V(G),E(H),\psi_H\big)$, where
\begin{align*}
	V(H)&=\{v_0,v_1,\cdots,v_5\},\quad E(H)=\{e_1,e_2,\cdots,e_{10}\}.\\
	\psi_H &\colon\begin{tabular}{ll}
		$e_i\mapsto v_iv_{i+1},\quad i=1,2,3,4;$ & $e_5\mapsto v_5v_1;$ \\
		$e_j\mapsto v_0v_{j-5},\quad j=6,7,8,9,10.$ & 
	\end{tabular}
\end{align*}
\end{example}
\begin{definition}[顶点, 边]
	图的图像表示不过是描述了其顶点与边的关联关系, 但我们通常将图的图像表示画出来之后就将其称为图本身, 在这种情况下, 我们也把图像表示中的点称为\textbf{``顶点''}(`vertices'), 点间连线称为\textbf{``边''}(`edges').
	\footnote{
	A diagram of a graph merely depicts the incidence relation holding between its vertices and edges. However, we often draw a diagram of a graph and refer to it as the graph itself; in the same spirit, we call its points `vertices' and its lines `edges'.}
\end{definition}

\begin{definition}[关联, 相邻]
	一条边的顶点与这条边\textbf{关联}(incident), 反之亦然.
	\footnote{这条边与其的一个顶点关联.}
	
	与同一条边关联的两个顶点是\textbf{相邻的}(adjacent), 与同一顶点关联的两条边也是相邻的, 我们称两个不同的相邻顶点是\textbf{邻点}(neighbours).
	\footnote{The ends of an edge are said to be incident with the edge, and vice versa. Two vertices which are incident with a common edge are adjacent, as are two edges which are incident with a common vertex, and two distinct adjacent vertices are neighbours.}
\end{definition}

\begin{definition}对于图$G$而言, 顶点$v$在其中的邻点集用$N_G(v)$, 进一步若限制在子图$S\subseteq G$上, 用$N_S(v)$表示.
\footnote{The set of neighbours of a vertex $v$ in a graph $G$ is denoted by $N_G(v)$.}
	\begin{align*}
		N_G(v)=&\sharp\big\{\text{neighbours of a vertex $v$ in graph $G$}\big\}\\
		N_S(v)=&\sharp\big\{\text{neighbours of a vertex $v$ in subgraph $S\subseteq G$}\big\}
	\end{align*}
\end{definition}

\begin{definition}[环, 连接, 重边]
	具有相同顶点的边称为一个\textbf{环}(loop), 具有不同顶点的边称为一个\textbf{连接}(link). 两个或多个有相同端点的连接被称为\textbf{重边}(parallel edges).
	\footnote{An edge with identical ends is called a loop, and an edge with distinct ends a link. Two or more links with the same pair of ends are said to be parallel edges. }
\end{definition}

\begin{definition}[有限图, 零图, 平凡图]
	一个图被称为\textbf{有限的}(finite), 如果它的顶点集和边集都是有限集. 没有顶点(也因此没有边)的图被称为\textbf{零图}(null graph). 任何只有一个顶点的图称为\textbf{平凡的}(trivial), 所有其他图则是\textbf{非平凡的}(nontrivial).
	\footnote{A graph is finite if both its vertex set and edge set are finite. The graph with no vertices (and hence no edges) is the null graph. Any graph with just one vertex is referred to as trivial. All other graphs are nontrivial. We admit the null graph solely for mathematical convenience.}
\end{definition}

\begin{definition}[简单图]
	一个图被称为\textbf{简单的}(simple), 如果图中不含环或重边.
	\footnote{A graph is simple if it has no loops or parallel edges.}
\end{definition}
\subsection{Special Families of Graphs}
我们讨论一些special families of graphs.
\footnote{Certain types of graphs play prominent roles in graph theory. A complete graph is a simple graph in which any two vertices are adjacent, an empty graph one in which no two vertices are adjacent (that is, one whose edge set is empty). A graph is bipartite if its vertex set can be partitioned into two subsets $X$ and $Y$ so that every edge has one end in $X$ and one end in $Y$ ; such a partition $(X,Y)$ is called a bipartition of the graph, and $X$ and $Y$ its parts. We denote a bipartite graph $G$ with bipartition $(X,Y)$ by $G[X,Y]$. If $G[X,Y]$ is simple and every vertex in $X$ is joined to every vertex in $Y$ , then $G$ is called a complete bipartite graph. A star is a complete bipartite graph $G[X,Y]$ with $|X|= 1$ or $|Y |= 1$. }

\begin{definition}[完全图]
	一个\textbf{完全图}(complete graph)是一个简单图, 其中任意两个顶点是相邻的.
\end{definition}

\begin{definition}[空图]
	一个图称为是\textbf{空图}(empty graph), 若其边集为空.
\end{definition}

\begin{definition}[二部图]
	一个图称为是\textbf{二部图}(bipartite graph), 若该图的顶点集可以划分称两个子集$X$和$Y$, 使得任意一条边的端点分别在$X$和$Y$中, 这种划分被称为图的一个\textbf{二划分}(bipartition), $X$和$Y$是图的两部份.我们用$G[X,Y]$表示一个二部图$G$有一个二划分$(X,Y)$. 若进一步, $G$是简单的, 且$X$中的每一个顶点连接了$Y$中的每一个顶点, 则称$G$是一个\textbf{完全二部图}(complete bipartite graph).
\end{definition}

\begin{definition}[星图]
	一个图称为是\textbf{星图}, 若其实一个完全二部图$G[X,Y]$, 且$|X|=1$或$|Y|=1$.
\end{definition}

\begin{definition}[path, cycle]
	A \textbf{path}(路) is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. Likewise, a \textbf{cycle}(圈) on three or more vertices is a simple graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise; a cycle on one vertex consists of a single vertex with a loop, and a cycle on two vertices consists of two vertices joined by a pair of parallel edges. The \textbf{length}(长度) of a path or a cycle is the number of its edges. A path or cycle of length $k$ is called a \textbf{$k$-path} or \textbf{$k$-cycle}, respectively; the path or cycle is odd or even according to the parity of $k$. A $3$-cycle is often called a \textbf{triangle}, a $4$-cycle a \textbf{quadrilateral}, a $5$-cycle a \textbf{pentagon}, a $6$-cycle a \textbf{hexagon}, and so on.
\end{definition}

\begin{proposition}
	Every path is bipartite.
\end{proposition}

\begin{proposition}
	A cycle is bipartite iff its length is even. 
\end{proposition}

\begin{definition}[$n$-cube]
	 The \textbf{$n$-cube}($n$-立方图) $Q_n$ ($n\geqslant 1$) is the graph whose vertex set is the set of all $n$-tuples of $0$s and $1$s, where two $n$-tuples are adjacent if they differ in precisely one coordinate.
\end{definition}

\begin{proposition}
	$Q_n$ is bipartite for all $n\geqslant 1$.
\end{proposition}

\begin{definition}[connected]
	A graph is \textbf{connected}(连通的) if, for every partition of its vertex set into two nonempty sets $X$ and $Y$ , there is an edge with one end in $X$ and one end in $Y$ ; otherwise the graph is \textbf{disconnected}(不连通的). In other words, a graph is disconnected if its vertex set can be partitioned into two nonempty subsets $X$ and $Y$ so that no edge has one end in $X$ and one end in $Y$ .
	\footnote{It is instructive to compare this definition with that of a bipartite graph.}
\end{definition}

For the sake of clarity, we observe certain conventions in representing graphs by diagrams: we do not allow an edge to intersect itself, nor let an edge pass through a vertex that is not an end of the edge; clearly, this is always possible. However, two edges may intersect at a point that does not correspond to a vertex.

\begin{definition}[planar graph, planar embedding]
	A graph which can be drawn in the plane in such a way that edges meet only at points corresponding to their common ends is called a \textbf{planar graph}(平面图), and such a drawing is called a \textbf{planar embedding}(平面嵌入) of the graph.
	\footnote{Whether a graph $\cong$ a planar graph is a problem worthy of attention.}
\end{definition}

Although not all graphs are planar, every graph can be drawn on some surface so that its edges intersect only at their ends. Such a drawing is called an \textbf{embedding}(嵌入) of the graph on the surface.

\begin{definition}[boolean lattice]
	 The \textbf{boolean lattice} $\operatorname{BL}_n$ ($n\geqslant 1$) is the graph whose vertex set is the set of all subsets of $\{1,2,\cdots,n\}$, where two subsets $X$ and $Y$ are adjacent if their symmetric difference (对称差) has precisely one element.
\end{definition}

\begin{proposition}
	$\operatorname{BL}_n$ is bipartite for all $n\geqslant 1$.
\end{proposition}

\subsection{Incidence and Adjacency Matrices}
接下来介绍图的incidence and adjacency matrices.
\footnote{Although drawings are a convenient means of specifying graphs, they are clearly not suitable for storing graphs in computers, or for applying mathematical methods to study their properties. For these purposes, we consider two matrices associated with a graph, its incidence matrix and its adjacency matrix.}

\begin{definition}[incidence matrix]
	Let $G$ be a graph, with vertex set $V(G)$ and edge set $E(G)$. The \textbf{incidence matrix}(关联矩阵) is the $|V(G)|\times |E(G)|$ matrix $\mathbf M(G):=(m_{ve})$, where $m_{ve}$ is the number of times ($0$, $1$, or $2$) that vertex $v$ and edge $e$ are incident.
	\footnote{Clearly, the incidence matrix is just another way of specifying the graph.}
\end{definition}

\begin{definition}[adjacency matrix]
	 Let $G$ be a graph, with vertex set $V(G)$ and edge set $E(G)$. The \textbf{adjacency matrix}(邻接矩阵) is the $|V(G)|\times |V(G)|$ matrix $\mathbf A(G):=(a_{uv})$, where $a_{uv}$ is the number of edges joining vertices $u$ and $v$, each loop counting as two edges.
\end{definition}

Because most graphs have many more edges than vertices, the adjacency matrix of a graph is generally much smaller than its incidence matrix and thus requires less storage space.

\begin{definition}[bipartite adjacency matrix]
	
\end{definition}
\subsection{Vertex Degrees}
Another important concept is the degree of a vertex.
\begin{definition}[degree]
	The \textbf{degree}(度) of a vertex $v$ in a graph $G$, denoted by $d_G(v)$\footnote{When there is no ambiguity, we use $d(v)$ simply.}, is the number of edges of $G$ incident with $v$, each loop counting as two edges. In particular, if $G$ is a simple graph, $d_G(v)$ is the number of neighbours of $v$ in $G$. A vertex of degree zero is called \textbf{isolated vertex}(孤立顶点).
	
	We denoted by $\delta(G)$ and $\Delta(G)$ the minimum and maximum degrees of the vertices of $G$, and by $d(G)$ their \textbf{average degree}(平均度数), i.e.
	\begin{align*}
		d(G)=\dfrac{1}{|V(G)|}\sum\limits_{v\in V(G)}d_G(v).
	\end{align*}
\end{definition}

\begin{theorem}
	For any graph $G$, we have
	\begin{align}\label{eq:1-woshou}
		\sum\limits_{v\in V(G)}d_G(v)\equiv 0\,\,(\operatorname{mod}2).
	\end{align}
\end{theorem}
\begin{proof}
	It is only necessary to consider that each edge is counted twice.
\end{proof}

\begin{corollary}
	In any graph, the number of vertices of odd degree is even.
\end{corollary}
\begin{proof}
	Proof by contradiction. Note the equation \eqref{eq:1-woshou}.
\end{proof}

\begin{definition}[$k$-regular]
	A graph $G$ is \textbf{$k$-regular}($k$-正则的) if $d_G(v)=k$ for all $v\in V(G)$.
\end{definition}

\section{Isomorphisms and Automorphisms}
\subsection{Isomorphisms}
Two graphs $G$ and $H$ are \textbf{identical}(相同的), written $G=H$, if $V(G)=V(H)$, $E(G)=E(H)$, and $\psi_G=\psi_H$. If two graphs are identical, they can clearly be represented by identical diagrams. However, it is also possible for graphs that are not identical to have essentially the same diagram.
For example, the graph $G$ and $H_1$ in Figure \ref{fig:1-2_isomorphism} can be represented by diagrams which look exactly the same, as the graph $H_2$ shows. The sole difference lies in the labels of their vertices and edges. Although the graph $G$ and $H$ are not identical, they do have the same structures, and are said to be isomorphic(同构的).

\begin{figure}[htbp!]
	\centering
	\subfloat[$G$]{
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=3,L=$a$]{a}
		\Vertex[x=3,y=3,L=$b$]{b}
		\Vertex[x=3,y=0,L=$c$]{c}
		\Vertex[x=0,y=0,L=$d$]{d}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
		\Edge[label=$e_3$](a)(b)
		\Edge[label=$e_5$](b)(c)
		\Edge[label=$e_6$](c)(d)
  		\tikzstyle{EdgeStyle}=[bend left]
  		\Edge[label=$e_2$](a)(d)
  		\tikzstyle{EdgeStyle}=[bend right]
  		\Edge[label=$e_1$](a)(d)
  		\tikzstyle{EdgeStyle}=[loop, looseness=20, out=-165, in=-105]
  		\Edge[label=$e_4$](b)(b)
  		%\node at (1,-1.6){$G$};
	\end{tikzpicture}
	}\quad\quad
	\subfloat[$H_1$]{
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=3,L=$w$]{a}
		\Vertex[x=3,y=3,L=$x$]{d}
		\Vertex[x=3,y=0,L=$z$]{b}
		\Vertex[x=0,y=0,L=$y$]{c}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
		\Edge[label=$f_5$](b)(c)
  		\tikzstyle{EdgeStyle}=[bend left]
  		\Edge[label=$f_4$](a)(d)
  		\tikzstyle{EdgeStyle}=[bend right]
  		\Edge[label=$f_3$](a)(d)
  		\Edge[label=$f_2$](c)(d)
  		\Edge[label=$f_1$](a)(b)
  		\tikzstyle{EdgeStyle}=[loop, looseness=20, out=75, in=15]
  		\Edge[label=$f_6$](b)(b)
		%\node at (0,-3){$H$};
	\end{tikzpicture}
	}\quad\quad
	\subfloat[$H_2$]{
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=3,L=$w$]{a}
		\Vertex[x=3,y=3,L=$z$]{b}
		\Vertex[x=3,y=0,L=$y$]{c}
		\Vertex[x=0,y=0,L=$x$]{d}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
		\Edge[label=$f_1$](a)(b)
		\Edge[label=$f_5$](b)(c)
		\Edge[label=$f_2$](c)(d)
  		\tikzstyle{EdgeStyle}=[bend left]
  		\Edge[label=$f_4$](a)(d)
  		\tikzstyle{EdgeStyle}=[bend right]
  		\Edge[label=$f_3$](a)(d)
  		\tikzstyle{EdgeStyle}=[loop, looseness=20, out=-165, in=-105]
  		\Edge[label=$f_6$](b)(b)
  		%\node at (1,-1.6){$G$};
	\end{tikzpicture}
	}
	\caption{Isomorphic graphs}
	\label{fig:1-2_isomorphism}
\end{figure}

\begin{definition}[isomorphic]
	Two graphs $G$ and $H$ are \textbf{isomorphic}(同构的), written $G\cong H$, if there are bijections(双射) $\theta\colon V(G)\to  V(H)$and $\phi\colon E(G)\to E(H)$ s.t. $\psi_G(e)=uv \iff \psi_H(\phi(e))=\theta(u)\theta(v)$. Such a pair of mapping is called an \textbf{isomorphism}(同构映射) between $G$ and $H$.
	\footnote{In the case of simple graphs, the definition of isomorphism can be stated more concisely, because if $(\theta,\phi)$ is an isomorphism between simple graphs $G$ and $H$, the mapping $\phi$ is completely determined by $\theta$. Indeed, $\phi(e)=\theta(u)\theta(v)$ for any edge $e=uv$ of $G$. Thus one may define an isomorphism between two simple graphs $G$ and $H$ as a bijection $\theta\colon V(G)\to V(H)$ which preserves adjacency (that is , the vertices $u$ and $v$ are adjacent in $G$ iff their images $\theta(u)$ and $\theta(v)$ are adjacent in $H$).}
\end{definition}

In order to show that two graphs are isomorphic, one must indicate an isomorphism between them. The pair of mappings $(\theta,\phi)$ defined by 
\begin{align*}
	\theta:=\left(\begin{tabular}{llll}
		$a$ & $b$ & $c$ & $d$\\
		$w$ & $z$ & $y$ & $x$
	\end{tabular}\right)\quad\quad\phi:=\left(\begin{tabular}{llllll}
		$e_1$ & $e_2$ & $e_3$ & $e_4$ & $e_5$ & $e_6$\\
		$f_3$ & $f_4$ & $f_1$ & $f_6$ & $f_5$ & $f_2$
	\end{tabular}\right)
\end{align*}
is an isomorphism between the graphs $G$ and $H$ in Figure \ref{fig:1-2_isomorphism}.
\footnote{Isomorphic graphs clearly have the same numbers of vertices and edges. On the other hand, equality of these parameters does not guarantee isomorphism.}

It is clear from the foregoing discussion that if two graphs are isomorphic, then they are either identical or diﬀer merely in the names of their vertices and edges, and thus have the same structure. Because it is primarily in structural properties that we are interested, we often omit labels when drawing graphs; formally, we may define an \textbf{unlabelled graph}(不含名称标记的图) as a representative of an equivalence class of isomorphic graphs. We assign labels to vertices and edges in a graph mainly for the purpose of referring to them (in proofs, for instance).

Up to isomorphism, there is just one complete graph on $n$ vertices, denoted $K_n$. Similarly, given two positive integers m and n, there is a unique complete bipartite graph with parts of sizes $m$ and $n$ (again, up to isomorphism), denoted $K_{m,n}$. Likewise, for any positive integer $n$, there is a unique path on $n$ vertices and a unique cycle on $n$ vertices. These graphs are denoted $P_n$ and $C_n$, respectively.
\subsection{Automorphisms}
\begin{definition}[automorphism]
	An \textbf{automorphism}(自同构) of a graph is an isomorphism of the graph to itself. In the case of simple graph, an automorphism is just a permutation(排列) of its vertex set which preserve adjacency: if $uv$ is an edge of edge then so is $\alpha(u)\alpha(v)$. 
\end{definition}

\begin{definition}
	The automorphisms of a graph reflect its symmetries(对称). For example, if $u$ and $v$ are two vertices of a simple graph, and if there is an automorphism $\alpha$ which maps $u$ to $v$, then $u$ and $v$ are alike in the graph, and are referred to as \textbf{similar vertices}(相似顶点). Graphs in which all vertices are similar, such as the complete graph $K_n$, the complete bipartite graph $K_{m,n}$ and the $n$-cube $Q_n$, are called \textbf{vertex-transitive}(顶点可传递的). Graphs in which no two vertices are similar are called \textbf{asymmetric}(非对成图); these are the graphs which have only the identity permutation as automorphism.
\end{definition}
\begin{example}[Petersen graph]
	
\end{example}

\begin{definition}[automorphism group]
	We denote the set of all automorphisms of a graph $G$ by $\operatorname{Aut}(G)$, and their number by $\operatorname{aut}(G)$. It can be verified that $\operatorname{Aut}(G)$ is a group under the operation of composition. This group is called the \textbf{automorphism group}(自同构群) of $G$.
\end{definition}

\subsection{Labelled Graphs}
\section{Graphs Arising from Other Structures}
\section{Constructing Graphs from Other Graphs}
\section{Directed Graphs}
A directed graph is a graph in which each link has an assigned orientation. 
\footnote{Although many problems lend themselves to graph-theoretic formulation, the concept of a graph is sometimes not quite adequate. When dealing with problems of traﬃc flow, for example, it is necessary to know which roads in the network are one-way, and in which direction traﬃc is permitted. Clearly, a graph of the network is not of much use in such a situation. What we need is a graph in which each link has an assigned orientation, namely a directed graph.}
\begin{definition}
	Formally, a \textbf{directed graph}(有向图) $D$ is an order pair $(V(D),A(D))$ consisting of a set $V:=V(D)$ of \textbf{vertices} and a set $A:=A(D)$, disjoint from $V(D)$, of \textbf{arcs}(弧), together with an \textbf{incidence dunction} $\psi_D$ that associated with each arc of $D$ an ordered pair of (not necessarily distinct) vertices of $D$. 
	
	If $a$ is an arc and $\psi_D(a)=(u,v)$, then $a$ is said to \textbf{join} $u$ to $v$; we also say that $u$ \textbf{dominates} $v$. The vertex $u$ is the \textbf{tail} of $a$, and the vertex $v$ its \textbf{head}; they are the two \textbf{ends} of $a$. 
	
	Occasionally, the orientation of an arc is irrelevant to the discussion. In such instances, we refer to the arc as an \textbf{edge} of the directed graph. The number of arcs in $D$ is donates by $a(D)$. The vertices which dominate a vertex $v$ are its \textbf{in-neighbours}(内邻), those which are dominated by the vertex its \textbf{outneighbours}(外邻). These sets are denoted by $N_D^-(v)$ and $N_D^+(v)$, respectively. 
\end{definition}

\begin{rmk}
	For convenience, we abbreviate the term `directed graph' to \textbf{digraph}. A \textbf{strict} digraph is one with no loops or parallel arcs (arcs with the same head and the same tail).
\end{rmk}

\section{Infinite Graphs}

\chapter{子图}
\section{Subgraphs and Supergraphs}
\subsection{Edge and Vertex Deletion}
\subsection{Maximality and Minimality}
\subsection{Acyclic Graphs and Digraphs}

\section{Spanning and Induced Subgraphs}
\subsection{Spanning Subgraphs}
\subsection{Induced Subgraphs}
\subsection{Weighted Graphs and Subgraphs}

\section{Modifying Graphs}
\section{Decompositions and Coverings}
\section{Edge Cuts and Bonds}
\section{Even Subgraphs}
\section{Graph Reconstruction}

\chapter{连通图}


\chapter{树}
\section{Forests and Trees}
\subsection{Rooted Trees and Branchings}
\section{Spanning Trees}
\subsection{Cayley's Formula}
\section{Fundamental Cycles and Bonds}
\subsection{Cotrees}

\chapter{Tree-Search Algorithms}
\section{Tree-Search}
\subsection{Breadth-First Search and Shortest Paths}
\subsection{Depth-First Search}
\subsection{Finding the Cut Vertices and Blocks of a Graph}
\section{Minimum-Weight Spanning Trees}
\section{Branching-Search}
\subsection{Finding Shortest Paths in Weighted Digraphs}
\subsection{Directed Depth-First Search}
\subsection{Finding the Strong Components of a Digraph}





\iffalse
\chapter{这里是章}
这里是章.
\section{这里是节}
这里是节.
\subsection{这里是子节}
这里是子节.
\subsubsection{这是子子节}
这里是子子节.
\paragraph{这里是段}
这里是段. 行内公式利用 \(1+2=3\) 或 $1+2=3$.

双换行以起到换行的效果. % 或这用 \par 来换行

	\begin{figure}[htbp]%这是一个图片插入模版
		\centering
		\includegraphics[width=0.5\textwidth]{../模版/pic1}
		\caption{这里是标签}
		\label{fig:test}%这里是交叉应用
	\end{figure}
这是一个图片示例. 

\begin{lstlisting}
# 示例：Python斐波那契数列
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

print("前10项斐波那契数列：")
for i in range(10):
    print(fib(i), end=" ")
\end{lstlisting}

图\ref{fig:abc},\ref{subfig:1}
\begin{figure}[htbp]
	\centering
	\caption{aaa}
	\label{fig:abc}
	\subfloat[子标题1]{
	\label{subfig:1}
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=0]{A1}
		\Vertex[x=5,y=5]{B2}
		\Vertex[x=3,y=0]{C3}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
  		\tikzstyle{EdgeStyle}=[bend left, red, -stealth]%向左弯曲, 红色, 箭头
  		\Edge[label=$120$](A1)(B2)
  		\Edge[label=$220$](B2)(C3)
	\end{tikzpicture}
	}
	\subfloat[子标题2]{
	\begin{tikzpicture}[scale=0.75,transform shape]
		\Vertex[x=0,y=0]{A1}
		\Vertex[x=5,y=5]{B2}
		\Vertex[x=3,y=0]{C3}
		\tikzstyle{LabelStyle}=[fill=white,sloped]
  		\tikzstyle{EdgeStyle}=[bend left, red, -stealth]%向左弯曲, 红色, 箭头
  		\Edge[label=$120$](A1)(B2)
  		\Edge[label=$220$](B2)(C3)
	\end{tikzpicture}
	}
\end{figure}
\newpage % 换页

	\begin{table}[!htbp]
	\centering
	\setlength{\abovecaptionskip}{3pt} % caption与表格之间的距离
	\caption{常见光滑(整体)截面}
	\vspace{1pt}
	\label{table-jiemian} % 交叉引用
	\resizebox{\textwidth}{!}{
		\begin{tabular}{ccc}
			\toprule[1.5pt]
			\makebox[0.2\textwidth]{丛类型} & \makebox[0.2\textwidth]{截面名称} & \makebox[0.5\textwidth]{直观含义(随点连续)} \\ % 一般使得和为0.9 textwidth
			\midrule
			切丛$T_M$ & 向量场 & 给每个点分配一个切向量\\
			余切丛$T_M^\star$ & $1$-形式场 &  给每个点分配一个余切函数\\
			外$k$-形式丛$ $ & $k$-形式场 & 给每个点分配一个反对称$k$阶张量\\
			张量丛$(T_M)_r^s$ & 张量场 & 给每个点分配一个$(r,s)$-型张量\\
			\bottomrule[1.5pt]
		\end{tabular}
	}
	\end{table}
这是一个表格示例.

\begin{theorem}[标题]
	这里是定理.
	
	注意, 首段落不会缩进, 这符合一般的论文格式(如springer Nature \LaTeX), 之后的段落将会自动缩进.
\end{theorem}
\begin{proof}
	\begin{align}
		f^{-1}\colon G\times G\to G\times G,\quad (a,c)\mapsto(a,a^{-1}c).
	\end{align}
	这部分为宋体?
\end{proof}

	\begin{center}
		\begin{tikzcd}[row sep=0.5em]
			G \arrow[r,"i_e"] & G\times G\arrow[r,"f^{-1}"] & G\times G\arrow[r,"\pi_2"] & G\\
			a\arrow[r,mapsto] & (a,e)\arrow[r,mapsto] & (a,a^{-1})\arrow[r,mapsto] & a^{-1}
		\end{tikzcd}
	\end{center}

\begin{definition}[标题]
	这里是一个定义.
\end{definition}

\begin{example}
	这是一个例子.
\end{example}

\begin{proposition}
	这里是一个命题.
\end{proposition}	

\begin{lemma}
	这里是一个引理.
\end{lemma}	

\begin{corollary}
	这是一个推论.
\end{corollary}	

\begin{recall}
	这里是回忆.
\end{recall}	


\begin{rmk}
	这里是注释.\footnote{这是脚注.}
\end{rmk}

一些公式的例子.
\begin{align}
	W\stackrel{w.}{\longrightarrow}Q,\quad (W\not\cong Q).\notag \\
	\prod_{\substack{i\geqslant 1\\ i\neq j}}a_i^j\label{1}
\end{align}

\newpage
文本, 测试.
\fi

\newpage % 新起一页写参考文献.
\begin{thebibliography}{9}%宽度9
	\bibitem{a1} J.A.Bondy, U.S.R.Murty. Graph Theory[M]. Springer, 2008.
	\bibitem{a2} 邦迪. 图论及其应用[M]. 高等教育出版社, 2005.
\end{thebibliography}

\end{document}